//用快速排序的办法
//平均复杂度为n
//查找数组中第n大的数
public class CompareSelection extends Sort{
    public int find(int data[],int n)
    {
        int left=0,right=data.length-1;
       while(true)
       {
       int j=partition(data, left,right);
       if(n==j)
       {
        return data[j];
       }
       else if(n>j)
       {
          left=j+1;
       }
       else
       {
         right=j-1;
       }
    }
    }

    public int partition(int data[],int left,int right)
    {
        int i=left,j=right;
        while(true)
        {
         while(data[i]<=data[left])   //i的职责是找到比基准数要大的，所以小于的时候继续循环  i最后停的位置就是比基准数大的那个数的位置
         {
           if(i>j)
           {
             break;
           }
           i++;
           if(i>right)
           {
            break;
           }
         }
         while(data[j]>data[left])   //思路类上  不管比较结果如何，j--一定会执行 j最后停的位置是比基准数小的或者一样的那个数的位置
         {
           if(j<i)
           {
             break;
           }
           j--;
         }
         if(i<j)
         {
             Exchange(data,i,j); 
             i++;
             j--;
         }
         else
         {
             break;
         }
        }
        Exchange(data,left,j);
        return j;
    }

}
